package leetcode.每日一题;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2022/10/20 9:44 AM
 * @description：
 */
public class 第K个语法符号 {
    @Test
    public void test() {

    }

    class Solution {
        public int kthGrammar(int n, int k) {
            if (n == 1) return 0;
            // 在前半部分
            if (k <= 1 << n - 2) return kthGrammar(n - 1, k);
            // 后半部分，翻转
            return kthGrammar(n - 1, k - (1 << n - 2)) ^ 1;
        }
    }
}
